|
In probability theory, if a large number of events are all independent of one another and each has probability less than 1, then there is a positive (possibly small) probability that none of the events will occur. The Lovász local lemma (a weaker version was proved in 1975 by László Lovász and Paul Erdős in the article ''Problems and results on 3-chromatic hypergraphs and some related questions'') allows one to relax the independence condition slightly: As long as the events are "mostly" independent from one another and aren't individually too likely, then there will still be a positive probability that none of them occurs. It is most commonly used in the probabilistic method, in particular to give existence proofs. There are several different versions of the lemma. The simplest and most frequently used is the symmetric version given below. For other versions, see . ==Statements of the Lemma (symmetric version)== Let ''A1, A2,..., Ak'' be a series of events such that each event occurs with probability at most ''p'' and such that each event is independent of all the other events except for at most ''d'' of them. Lemma I (Lovász and Erdős 1973; published 1975) If Lemma II (Lovász 1977; published by Joel Spencer) If Lemma II today is usually referred to as "Lovász local lemma". Lemma III (Shearer 1985) If The threshold in lemma III is optimal and it implies that the bound : is also sufficient. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Lovász local lemma」の詳細全文を読む スポンサード リンク
|